class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0 for i in range(n+1)]
        #dp[i]表示i拆分的最大乘积
        dp[2] = 1
        for i in range(3, n+1):
            #j为最后一个数
            for j in range(1, i):
                dp[i] = max(dp[i], max((i-j) * j, j * dp[i-j]))
        return dp[n]
